package HeapSort;

/*
*       堆排序是通过 树 来实现的算法
*       要 排升序需要建立大根堆，排降序要建立小根堆
*/


import java.util.Arrays;

public class Heap {

    // Global variable that records the length of an array;
    static int heapLen;

    /**
     * Swap the two elements of an array
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * Build Max Heap
     * @param arr
     * 这里的这个方法实现的是建立大根堆的操作
     */
    private static void buildMaxHeap(int[] arr) {
        // 这里是要找到父节点，并且通过这里的父节点来实现大根堆的排序操作
        // 需要注意的是，这里获取的是数组中的元素，parent 的值是可以为 0 的
        for (int parent = arr.length / 2 - 1; parent >= 0; parent--) {
            heapify(arr, parent);
        }
    }

    /**
     * Adjust it to the maximum heap
     * @param arr
     * @param parent
     */
    private static void heapify(int[] arr, int parent) {
        // 这里定义出两个节点分别对应着父节点的左右两部分子树
        int left = 2 * parent + 1;
        int right = 2 * parent + 2;
        // 再定义出一个指针，指向 parent
        int largest = parent;
        if (right < heapLen && arr[right] > arr[largest]) {
            // 这里是针对右子树进行判断，如果右子树的值大于 当前根节点的值
            // 此时 就将 指向根节点的指针指向右子树
            // 以此来标记较大值
            largest = right;
        }
        if (left < heapLen && arr[left] > arr[largest]) {
            // 左子树也是同理
            largest = left;
        }
        // 只要当前标记最大值的指针不是指向原先的 父元素
        // 此时也就说明了 有比当前父元素大的值，要进行交换操作
        if (largest != parent) {
            // 进行交换操作
            swap(arr, largest, parent);

            // 在进行完一轮判断后，再次进入该方法进行寻找
            heapify(arr, largest);
        }
    }

    /**
     * Heap Sort
     * @param arr
     * @return
     */
    public static int[] heapSort(int[] arr) {
        // 向全局变量添加了数组 arr 的长度
        heapLen = arr.length;
        // 创建大根堆
        buildMaxHeap(arr);
        for (int i = arr.length - 1; i > 0; i--) {
            // 这里通过交换操作，将堆顶的较大值向数组的最后位置进行移动
            swap(arr, 0, i);
            // 因为数组尾部存储的都是有序列的值，此时需要进行 -1 操作减少前面无序范围
            heapLen -= 1;
            // 当然在前面进行交换之后，第一个 arr[0] 处的元素也就不在是排序后最大的了
            // 所以将其传入到排序的核心算法中进行计算即可
            heapify(arr, 0);
        }
        return arr;
    }



    public static void main(String[] args) {
        int[] arr = {9,8,7,6,4,5,1,2,3};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
